package practice.Day13;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @Author quan
 * @Description 跳石板
 * @Date 2023/5/22 10:48
 */
public class Num2_JumpStone {
    /**
     * 看了很久，也没看懂，用的是动态规划。下去先看一下动态规划吧！
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//4
        int m = sc.nextInt();//24
        //m+1是因为有m块石板，我们为了让石板下标与编号对应
        int[] step = new int[m+1];
        //初始化
        for (int i = 0; i < m+1; i++) {
            step[i] = Integer.MAX_VALUE;
        }
        step[n] = 0;
        //i表示当前石板编号
        for (int i = n; i < m; i++) {
            //无法跳跃到该位置
            if(step[i] == Integer.MAX_VALUE){
                continue;
            }
            //求一个数的约数的集合，不包括1和本身
            List<Integer> list = div(i);
            //遍历所有的约数
            for (int j : list) {
                //假设之前跳到i+j的石板路径为4，而跳到i的次数是2，那么现在i到i+j就是2+1为3次。
                //那么最新的最小次数就是step[i] +1
                if(i+j <=m && step[i+j]!=Integer.MAX_VALUE){
                    step[i+j] = Math.min(step[i+j],step[i]+1);
                } else if (i+j <= m) {
                    step[i+j] = step[i] + 1;
                }
            }
        }
        if(step[m] == Integer.MAX_VALUE){
            //调不到这个石板上
            System.out.println(-1);
        }else{
            System.out.println(step[m]);
        }
    }

    /**
     * 求约数
     * @param n
     * @return
     */
    private static List<Integer> div(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i*i <= n ; i++) {
            if(n%i==0){
                list.add(i);
                if(n/i!=i){
                    list.add(n/i);
                }
            }
        }
        return list;
    }
}
